import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lv
 * Date: 2023-03-16
 * Time: 15:00
 */
public class TestSort {

    /**
     * 直接插入排序
     * 时间复杂度：O(N^2)->最好的情况是 O(N)
     *      对于直接插入排序来说，数据越有序，越快
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 一个稳定的排序可以实现为不稳定的排序
     * 但是一个本身就不稳定的排序，不可以变成稳定的排序
     * 经常使用在 数据量不多 且整体数据趋于有序了
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ;j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    //array[j+1]=tmp;//只要j回退的时候，遇到了比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了小于0的地方
            array[j+1]=tmp;
        }
    }

    public static void insertSort2(int[] array,int start,int end){
        for (int i = 1; i < end; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=start ;j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    //array[j+1]=tmp;//只要j回退的时候，遇到了比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了小于0的地方
            array[j+1]=tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度[和增量有关系]：O(n^1.3~n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的
     *      看比较的过程中，是否发生了跳跃式的交换，如果发生了跳跃式的交换，那么就是不稳定的排序
     * @param array
     */
    public static void shell(int[] array,int gap){    // gap 组数
        for (int i = 1 ; i < array.length; i++) {
            int tmp=array[i];
            int j = i-gap;
            for (; j >=0 ;j-=gap) {
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1); //保证最后是一组
    }

    /**
     * 直接选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public static  void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }


    /**
     * 堆排序
     * 时间复杂度：O(N*log N)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        //1.建堆
        createHeap(array);
        int end= array.length-1;
        //2.交换然后调整
        while(end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static  void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent,int len){
        int child=2*parent+1;//左孩子下标
        while (child<len){
            if(child+1<len && array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }


    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 有序情况下：O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {//i 表示趟数
            boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {//j 交换次数
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(flg==false){
                break;
            }
        }
    }


    /**
     * 快速排序
     * (最好)时间复杂度：O(N*log n),    数据有序或者逆序  O(N^2)
     * (最好)空间复杂度：O(log n)
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort1(int[] array) {
        quick(array,0, array.length-1);
    }
    public static void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }

        //  优化 如果区间内的数字在排序的过程中小于某个范围了，可以直接使用插入排序
        if(right-left+1<5000){
            //直接使用插入排序
            insertSort2(array,left,right);
            return;
        }
        //

        //优化  找基准之前，我们找到中间大的值-->使用三数取中法
        int midValIndex=findMidValIndex(array,left,right);
        swap(array,midValIndex,left);
        //

        int pivot=partition(array,left,right);//基准
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
        //优化

    private static int findMidValIndex(int[] array,int start,int end){
        int mid=(start+end)/2;
        if(array[start] < array[end]){
            if(array[mid]<array[start]){
                return start;
            } else if (array[mid]>array[end]) {
                return end;
            }else{
                return mid;
            }
        }else{
            if(array[mid]>array[start]){
                return start;
            } else if (array[mid]<array[end]) {
                return end;
            }else{
                return mid;
            }
        }
    }
    //
    private static int partition(int[] array,int start,int end){  //找基准
        int tmp=array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            //end下标遇到了小于tmp的值
            array[start]=array[end];
            while(start < end && array[start] <= tmp){
                start++;
            }
            //start下标遇到了大于tmp的值
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }

    //非递归实现快速排序
    public static void quickSort2(int[] array){

        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);

        if(pivot>left+1){
            //左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot<right-1){
            //右边有两个元素
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition(array,left,right);

            if(pivot>left+1){
                //左边有两个元素
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1){
                //右边有两个元素
                stack.push(pivot+1);
                stack.push(right);
            }
        }

    }



    //合并两个有序数组
    public static int[] mergeArray(int[] array1,int[] array2){
        int[] tmp=new int[array1.length+array2.length];
        int k=0;
        int s1=0;
        int e1=array1.length-1;
        int s2=0;
        int e2=array2.length-1;

        while(s1<=e1 && s2<=e2){
            if(array1[s1] <= array2[s2]){
                tmp[k++]=array1[s1++];
                //s1++;
                //k++;
            }else{
                tmp[k++]=array2[s2++];
                //s2++;
                //k++;
            }
        }

        while(s1<=e1){
            tmp[k++]=array1[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array2[s2++];
        }
        return tmp;
    }
    /**
     * 归并排序
     * 时间复杂度：O(N*log n)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     *
     * 学过的排序 只有3个是稳定的
     * 冒泡，插入，归并
     * @param array
     */
    public static void mergeSort1(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }
    private static void mergeSortInternal(int[] array,int low,int high){

        if (low>=high){
            return;
        }

        int mid=(low+high)/2;
        //左边
        mergeSortInternal(array,low,mid);
        //右边
        mergeSortInternal(array,mid+1,high);
        //归并
        merge(array,low,mid,high);
    }
    private static void merge(int[] array,int low,int mid,int high){
        int[] tmp=new int[high-low+1];
        int k=0;
        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;
        while(s1<=e1 && s2<=e2){
            if(array[s1] <= array[s2]){
                tmp[k++]=array[s1++];
                //s1++;
                //k++;
            }else{
                tmp[k++]=array[s2++];
                //s2++;
                //k++;
            }
        }
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        //拷贝tmp当中的元素，放到原来的array数组当中
        for (int i = 0; i < k; i++) {
            array[i+low]=tmp[i];
        }
    }

    //非递归的归并排序
    public static void mergeSort2   (int[] array){
        int nums=1; //每组的数据个数

        while(nums<array.length){
            //数组每次都要进行遍历,确定要归并的区间
            for (int i = 0; i < array.length; i+=nums*2) {
                int left=i;
                int mid = left+nums-1;
                //防止越界
                if(mid >= array.length){
                    mid=array.length-1;
                }
                int right = mid+nums;
                if(right >= array.length){
                    right=array.length-1;
                }
                //下标确定之后开始合并
                merge(array, left,mid,right);
            }
            nums *= 2;
        }
    }


    /**
     *计数排序
     * 时间复杂度：O(N)
     * 空间复杂度：O(m)  m:代表当前数据的范围
     * 稳定性：不稳定
     * 一般适用于有n个数，数据范围是0~n 之间的
     * @param array
     */
    public static void countingSort(int[] array){
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i]<minVal){
                minVal=array[i];
            }
            if(array[i]>maxVal){
                maxVal=array[i];
            }
        }
        //说明已经找到了最大值和最小值
        int[] count=new int[maxVal-minVal+1];//默认都是0
        //统计array数组当中，每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int index=array[i];
            count[index-minVal]++;
        }
        //说明在计数数组当中，已经把array数组当中，每个数据出现的次数已经统计好了
        //接下来，只需要遍历计数数组
        int indexArray = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                //一定要加minVal，因为不一定就是i出现了count[i]
                array[indexArray]=i+minVal;
                count[i]--;//拷贝一个之后，次数也就少一个
                indexArray++;//下标得向后移动
            }
        }
    }


    public static void test2(int capacity){
        int[] array=new int[capacity];
        Random random=new Random();
        for (int i = 1; i < array.length; i++) {
            array[i]=random.nextInt(capacity);
        }
        long start=System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //quickSort1(array);
        long end=System.currentTimeMillis();
        System.out.println(end-start);
    }

    public static void test1(int capacity){
        int[] array=new int[capacity];
        for (int i = 0; i < array.length; i++) {
            array[i]=i;
        }
        long start=System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        quickSort1(array);
        long end=System.currentTimeMillis();
        System.out.println(end-start);
    }


    public static void main2(String[] args) {
        test1(10_0000);
        //test2(10_0000);
    }

    public static void main(String[] args) {
        int[] array={12,5,18,10,4,2};
        //insertSort(array);
        //shellSort(array);
        //shellSort(array);
        //heapSort(array);
        //bubbleSort(array);
        //quickSort2(array);
        //mergeSort2(array);
        countingSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void main0(String[] args) {
        int[] array1={1,3,5,7,9};
        int[] array2={2,4,6,8,10};
        int[] ret=mergeArray(array1,array2);
        System.out.println(Arrays.toString(ret));
    }
}
